The present invention relates to a constraint based routing scheme for a network, particularly but not exclusive to a routing scheme which adopts various constraint profiles which can be selected by a user and implemented by a network operator for a communications network.
Within the physical resources of a network, for example, within a network element, circuit switched traffic can follow paths and trails at various multiplex levels. A trail, for example, may be a circuit, line, path or section into which, at a first end, is inserted a data stream, and at a second end, is output the data stream.
Routing traffic across a network is becoming an increasingly complex task often requiring both manual and computational techniques to be combined. Computed routes may include network elements paths which are suitable for a variety of reasons. For example, whilst a network may support a variety of traffic types, however not all network elements may support a specific traffic type. If this route is to be used, then a container is needed to carry such traffic over the route between those network elements. Alternatively, those network elements must be avoided and another route needs to be selected.
For example, within a communications network, there may be a restricted number of network elements which are capable of processing voice data. Operations on voice data at a voice level may be performed within those particular network elements. However, to transport traffic data between those network elements, there must be further transmission, such as provided by a synchronous digital hierarchy (SDH) virtual container system.
As an example, if a voice connection is to be made between two geographically disparate network elements, the connection may be routed via intermediate network elements in the VC-12 layer. However, the VC-12 layer itself, to connect between intermediate network elements, may need to be multiplexed into a higher bit rate layer, e.g. the VC-4 layer.
Conventional trail routing schemes compute a number of potential routes and return these as potential routes to the network operator. The network operator must then select from the returned routes a suitable route bearing in mind any requests made by a user and the type of traffic to be routed. Trails computed conventionally will often include connections which are either physically and/or logically unsuitable. Conventional trail routing programs do not efficiently incorporate user preferences and/or desired routing profiles into the computation of the routes to eliminate the majority of unsuitable routes unless they are based on complex, for example genetic, algorithms. Such complex algorithms can incur extensive coding and, despite their complexity, often demonstrate a lack of versatility which creates implementation problems.
Conventional routing programs often implement Dijkstra algorithm based route selection scheme(s). These are more simple to implement in code than a genetic algorithm based route selection scheme. However, a problem associated with use of the Dijkstra algorithm is the high number of potential routes it returns from analysis at the abstract level which must then be confirmed as acceptable at the physical level either automatically or by a human operator intervening in the process.
The number of unsuitable routes selected in conventional Dijkstra based selection schemes can be extremely high, for example, in an optical network, Dijkstra based routing schemes often require subsequent verification of over a hundred possible routes. The elimination of redundant routes is often a time consuming process.
Users of a communications network providing routing services often request that a routing policy be used when a trail is being established. For example, when routing a trail consideration is often paid to criteria such as whether the trail will carry voice, data, video or graphics services, and the extent to which the trail maximises network asset utilization and minimises blocking. Accordingly, there is a demand for a network management system which can mediate between a required class of service requested by a user and the available quality of service which can be supported.
One object of the invention seeks to mitigate and/or obviate the above problems by providing a method of selecting a trail route which is able to support and enforce user selected policies independently of the treatment of each class of traffic within different networking scenarios.
Another object of the invention is to provide an route advising application which provides routing policy management, i.e., routing management which can be selectively based on one or more predetermined routing profiles or equivalently routing principles. Such routing profiles may be based on criteria such as, for example, a balancing mode criteria for balancing traffic across the network, a threshold level for link usage criteria, a cumulative path threshold level criteria, a diverse routing criteria, an exclusion profile criteria for excluding some network sector/traffic type, a Quality of Service criteria, a Class of Service criteria, and/or a User Information criteria. A profile formed from an appropriate combination of these criteria can then be used in route computation requests.
Another object of the invention thus seeks to provide a method of optimising a routing scheme for a network.
Another object of the invention seeks to provide a routing scheme for a network which enables a suitable route to be determined automatically by pre-weighting certain routes according to their likely appropriateness.
The routing scheme according to the invention enables a route to be preselected using the routing algorithm which reflects additional selection criteria than simply the shortest-path across a network, for example, a route can be preselected to balance load on the network more evenly. Moreover, only routes which are physically able to support a particular connection request can be selected. Other selection criteria such as the cost of a route may be incorporated into the routing scheme to influence route selection by the Dijkstra algorithm.
The pre-weighting is provided by modifying the weight given to a network link in a conventional routing algorithm such as a Dijkstra algorithm. This biasing of a conventional routing algorithm enables factors beyond simple topology to be taken into account.
A first aspect of the invention seeks to provide a method of selecting a trail route across a communications network using a routing engine, the method comprising the steps of: selecting a routing policy profile having at least one route biasing parameter; inputting information from said routing policy profile to said routing engine, in which said information includes information derived from said selected at least one route biasing parameter which biases the computation of trail routes; and computing a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy.
Preferably, the method is used to select trail routes for different classes of traffic within a network. The routing policy may bias the output of the routing engine independently of the manner in which said different classes of traffic are individually routed.
The step of selecting a routing policy profile may be performed by a user of the communications network, or by a network operator, or be performed automatically.
Preferably, at least one of said parameters is taken from the group consisting of:
a balancing mode criteria; a threshold level for link usage criteria; a cumulative path threshold level criteria; a diverse routing criteria; an exclusion profile criteria for excluding some network sector/traffic type; a Quality of Service criteria; a Class of Service criteria; and a User Information criteria.
Preferably, the routing engine comprises a Dijkstra algorithm.
The trail route selected may provide protection for a working path.
Preferably, if the trail route selected provides protection for a working path, the trail route selected may re-use at least one link along the working path having a higher capacity than any other available link.
A second aspect of the invention seeks to provide a routing application having a graphically displayed user interface arranged to enable the selection of a trail route across a communications network using a routing engine, the software comprising: selection means for a network operator of a communications network to select a routing policy profile having a plurality of parameters; input means to input information from said routing policy profile to said routing engine to bias the computation of trail routes; and computational means to compute a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy.
A third aspect of the invention seeks to provide a constraint based routing scheme for a communications network, the scheme comprising a method of selecting a trail route across a communications network using a routing engine, the method comprising the steps of: selecting a routing policy profile having a plurality of route constraining parameters which are capable of constraining the output of said routing engine; inputting information from said routing policy profile to said routing engine, wherein said inputted information includes said route constraining parameters to bias the computation of trail routes; and computing a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy information by the inputted route constraining parameters.
A fourth aspect of the invention seeks to provide apparatus arranged to implement a method of selecting a trail route across a communications network using a routing engine, the apparatus comprising: selection means arranged to enable a network operator to select a routing policy profile having a plurality of parameters; input means arranged to input information from said routing policy profile to said routing engine to bias the computation of trail routes; and computational means arranged to compute a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy.
A fifth aspect of the invention seeks to provide a route advising application providing routing policy management which can be selectively based on one or more routing policies, the routing policies having route biasing parameters which bias input into a Dijkstra based routing engine to constrain the number of routes output by the Dijkstra based routing engine to a set of at least one route which conforms with said routing policy.
Preferably, the said one or more routing profiles may be based on at least one criteria taken from the group consisting of: a balancing mode criteria for balancing traffic across the network, a threshold level for link usage criteria, a cumulative path threshold level criteria, a diverse routing criteria, an exclusion profile criteria for excluding some network sector/traffic type, a Quality of Service criteria, a Class of Service criteria, and/or a User Information criteria.
A sixth aspect of the invention seeks to provide a routing scheme for a network comprising:
applying a biasing factor to a network link in a network topology model;
providing input from said biased network topology model to a routing algorithm;
selecting a route from a subset of at least one potential routes generated by said routing algorithm.
Preferably, said biasing factor is a weight given to said network link to prejudice said muting algorithm from selecting said network link
More than one network link, which is a connection between two network nodes, or network elements, may be biased.
A seventh aspect of the invention include providing apparatus arranged to implement a routing scheme for traffic over a communications network according to the sixth aspect. An eighth aspect of the invention seeks to provide a system for routing traffic over a communications network, the system comprising apparatus arranged to implement the routing scheme according to the sixth aspect.
Advantageously, the invention enables customer specified trail routing policies took be supported.
Advantageously, by modifying a conventional Dijkstra based route selection schemes to incorporate additional selection criteria to eliminate the selection of unsuitable routes, a limited set of routes may be returned by the computational process, eliminating the need for extensive further review for physical/logical compatibility.
The invention is also directed to a method by which the described apparatus operates and including method steps for carrying out every function of the apparatus.
The invention also provides for a system for the purposes of digital signal processing which comprises one or more instances of apparatus embodying the present invention, together with other additional apparatus.
The preferred features may be combined as appropriate, as would be apparent to a skilled person, and may be combined with any of the aspects of the invention.
It is advantageous if an algorithm can be utilised which requires less time to implement and which enables a more rapid selection of a suitable route by a network operator.
In particular, in order to maintain the overall efficiency of a communications network, it is often desirable to route calls across the network in a manner which balances out the load on the network. Moreover, where protection needs to be provisioned in a network, it necessary to identify rapidly from the route(s) determined at an abstract network topology level as potentially suitable, a route or subset of routes having the required physical characteristics to support the connection.